class code3 {
    //全排列问题：决策树(回溯dfs)
    List<String> ret;
    boolean[] check;
    public String[] permutation(String s) {
        ret = new ArrayList<>();
        check = new boolean[s.length()];
        StringBuilder ss = new StringBuilder();
        dfs(ss, s);
        return ret.toArray(new String[ret.size()]);
    }

    public void dfs(StringBuilder ss, String s) {
        //递归出口：加入ret
        if(ss.length() == s.length()) {
            ret.add(ss.toString());
            return;
        }

        for(int i=0;i<s.length();i++) {
            //false代表没有用过
            if(!check[i]) {
                check[i] = true;
                ss.append(s.charAt(i));
                dfs(ss,s);
                //回溯
                ss.deleteCharAt(ss.length()-1);
                check[i] = false;
            }
        }
    }
}